1. Make sure the traveler server has access to your mailfile, check the ACL
2. try to run the command: tell traveler user CN=Firstname Lastname/O=Domain
2.1 Mailfile doesn not contain ID-File is not a problem
2.2 Entry not found in index is also not a problem, look for other problems
3. Make sure your traveler server can access the mail-server / cluster. Maybe you need to check dns or connection documents or network problems.
4. Try accessing the traveler server with the URL in the browser and check the status there. It should look like this:

Picture

When I run the command "tell traveler user..." i get this
Command Image

I have no trouble opening the URL in browhttp://www-10.lotus.com/ldd/ndseforum.nsf/xpReply.xsp?documentId=666CF149F3FC799D85257D96004A43BF&action=editDocumentser on device
Browser Image

EDIT: I seem to have come a little bit closer. When I go to this webpage Notes Traveler 9
And follow the guide "Connecting directly to IBM Notes Traveler"
I can connect with an Samsung Galaxy S2 and it's default mail app that handles Exchange but IBM Notes Traveler still does not work.

Well all looks good so far.

Have you done this steps:

1. Download the Traveler App from the Google Play store
2. Launch the App and enter your Travler server name (only DNS name no HTTP or HTTPS)
3. Enter the Username (can be the E-mail Adress or the common name)
4. Enter the Internet Password / Samtime password
5. Approve the device Request in your traveler server

1,2,3,4 I have done all these steps.

5. Server is set for the moment to authorize all devices.